package cn.aylog.simpleTree;

import java.util.Arrays;

/**
 * 堆排序，就是不断调整堆的过程
 * 大堆
 *  父节点大于等于左右子节点
 * 小堆
 *  父节点小于等于左右子节点
 */
public class HeapBinaryTreeDemo {
    public static void main(String[] args) {
        // int[] arr = {3, 5, 1, 77, 6, 9, -1, 23};
        int len = 8;
        int[] arr = new int[len];
        for(int i=0; i<len; i++) {
            arr[i] = (int)(Math.random()*8000000);
        }
        long start = System.currentTimeMillis();
        heapSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("排序耗时: " + (end - start));
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 升序排序（大堆）
     * 降序排序（小堆）
     */
    public static void heapSort(int[] arr) {
        int temp;
        int len = arr.length;
        // 先调整最左边的节点树
        for (int i = len / 2 - 1; i >= 0; i--) {
            adjustNode(arr, i, len-1);
        }
        // 遍历交换、比较
        for (int i = len - 1; i >= 0; i--) {
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustNode(arr, 0, i);
        }
    }

    /**
     * 节点比较和交换
     */
    public static void adjustNode(int[] arr, int n, int length) {
        int temp = arr[n];
        for (int i = 2 * n + 1; i < length; i = 2 * i + 1) {
            // 指定节点n的左右子节点比较
            // if (i+1 < length &&  arr[i] < arr[i + 1]) { // 大堆
            if (i+1 < length &&  arr[i] > arr[i + 1]) {
                i++;
            }
            // 父节点与子节点比较，交换
            // if (arr[i] > temp) { // 小堆
            if (arr[i] < temp) {
                arr[n] = arr[i];
                n = i;
            } else {
                break;
            }
        }
        arr[n] = temp;
    }
}
